package leetcode.weekly.week290;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution4 implements IDebug {

	private class Node {
		private int LeftRange, Mid, RightRange;
		private Node leftChild, rightChild;
		private Integer value;

		public Node(int left, int right) {
			this.LeftRange = left;
			this.RightRange = right;
			this.Mid = ((this.RightRange - this.LeftRange) >> 1) + this.LeftRange;
			this.value = 0;
		}

		private Node leftNode() {
			if (this.leftChild == null) {
				this.leftChild = new Node(this.LeftRange, this.Mid);
			}
			return this.leftChild;
		}

		private Node rightNode() {
			if (this.rightChild == null) {
				this.rightChild = new Node(this.Mid + 1, this.RightRange);
			}
			return this.rightChild;
		}

		private void addValue(int value) {
			this.value = this.value == null ? value : this.value + value;
		}

		public void add(int left, int right, int add) {
			if (left > right) {
				return;
			}
			if (left == this.LeftRange && right == this.RightRange) {
				this.addValue(add);
			} else {
				pushdown();
				this.leftNode().add(left, Math.min(this.Mid, right), add);
				this.rightNode().add(Math.max(this.Mid + 1, left), right, add);
			}
		}

		public int query(int index) {
			if (this.LeftRange == index && index == this.RightRange) {
				return value;
			}
			pushdown();
			if (index <= this.Mid) {
				return this.leftNode().query(index);
			}
			return this.rightNode().query(index);
		}

		private void pushdown() {
			if (this.value != null) {
				this.leftNode().addValue(this.value);
				this.rightNode().addValue(this.value);
				this.value = null;
			}
		}
	}

	public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
		Node node = new Node(1, (int) 1e9);
		for (int i = 0; i < flowers.length; i++) {
			int[] flower = flowers[i];
			node.add(flower[0], flower[1], 1);
		}
		int len = persons.length;
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			ans[i] = node.query(persons[i]);
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(H.str2array3("[1,2,2,2]"),
				this.fullBloomFlowers(H.str2array1("[[1,6],[3,7],[9,12],[4,13]]"), H.str2array3("[2,3,7,11]")));

	}

	@Override
	public void debug3() {
		H.compare(H.str2array3("[2,2,1]"),
				this.fullBloomFlowers(H.str2array1("[[1,10],[3,3]]"), H.str2array3("[3,3,2]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
